'''
https://leetcode.cn/problems/max-stack
'''
from sortedcontainers import SortedList

class MaxStack:
    print()

    def __init__(self):
        self.stack = SortedList()   # (id, val)
        self.value = SortedList()   # (val, id)
        self.id = 0

    def push(self, x: int) -> None:
        self.stack.add((self.id, x))
        self.value.add((x, self.id))
        self.id += 1

    def pop(self) -> int:
        id, x = self.stack.pop()
        self.value.remove((x, id))
        return x

    def top(self) -> int:
        return self.stack[-1][1]

    def peekMax(self) -> int:
        return self.value[-1][0]

    def popMax(self) -> int:
        x, id = self.value.pop()
        self.stack.remove((id, x))
        return x
